﻿
public class TreeNode {
    public int val;
    public TreeNode left;
    public TreeNode right;
    public TreeNode(int val=0, TreeNode left=null, TreeNode right=null) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}

public class Solution {
    public int Rob(TreeNode root)
    {
        int[] res = RobArr(root);

        return res.Max();
    }

    private int[] RobArr(TreeNode root)
    {
        // 偷，不偷 -- 所对应的金额
        if (root is null) return [0, 0];

        int[] resLeft = RobArr(root.left);
        int[] resRight = RobArr(root.right);
        
        // 偷
        int res1 = root.val + resLeft[1] + resRight[1];
        
        // 不偷
        int res2 = resLeft.Max() + resRight.Max();
        return [res1, res2];
    }

    public static void Main(string[] args)
    {
        int?[] root = [3, 2, 3, null, 3, null, 1];
        TreeNode rootNode = CreateBinaryTree(root);
        Solution solution = new Solution();
        int res = solution.Rob(rootNode);
        Console.WriteLine(res);
    }
    
    // 构造树
    public static TreeNode CreateBinaryTree(int?[] root)
    {
        if (root is null || root.Length == 0) return null;
        
        Queue<TreeNode> queue = new Queue<TreeNode>();
        
        TreeNode rootNode = new TreeNode(root[0].Value);
        queue.Enqueue(rootNode);
        TreeNode node;
        int i = 1;
        while (i < root.Length && queue.Count > 0)
        {
            bool flag = true;
            node = queue.Dequeue();
            if (root[i] is not null)
            {
                node.left = new TreeNode(root[i].Value);
                queue.Enqueue(node.left);
                flag = false;
            }

            i++;
            if (i >= root.Length) break;
            if (root[i] is not null)
            {
                node.right = new TreeNode(root[i].Value);
                queue.Enqueue(node.right);
                flag = false;
            }

            i++;
            if (flag)
            {
                queue.Enqueue(node);
            }
        }

        return rootNode;
    }
}